// 从二叉树的中序和后续遍历序列 获取前序遍历序列
#include <iostream>
#include <string>

using namespace std;

string get_preorder(string h, string z) {
	
	int n = h.length();
	
	if(h.length() == 0 || h.length() == 1)
		return h;
	
	char c = h[h.length()-1];
	
	
	int pos = z.find(c);
	string z_left = z.substr(0, pos);
	string z_right = z.substr(pos+1,n-pos-1);
	
	string h_left = h.substr(0, pos);
	string h_right = h.substr(pos, n-pos-1);
	
	
	string q_left = get_preorder(h_left, z_left);
	string q_right = get_preorder(h_right, z_right);
	
	string q(1, c);
	  	q += q_left;
	  	q += q_right;
	return q;
	
	
}
int main()
{
	string h = "DGJHEBIFCA"; // 后序遍历序列 
	string z = "DBGEHJACIF"; // 中序遍历序列
	
	string q = get_preorder(h, z);
	
	cout << q << endl;
	
	return 0;
}
